Một trong những kết quả đầu tiên trong lý thuyết đồ thị xuất hiện trong bài báo của Leonhard Euler về Bảy cây cầu ở Königsberg, xuất bản năm 1736. Bài báo này cũng được xem như một trong những kết quả topo đầu tiên trong hình học, tức là, nó không hề phụ thuộc vào bất cứ độ đo nào. Nó diễn tả mối liên hệ sâu sắc giữa lý thuyết đồ thị và tôpô học.

Năm 1845, Gustav Kirchhoff đưa ra Định luật Kirchhoff cho mạch điện để tính điện thế và cường độ dòng điện trong mạch điện.

Năm 1852 Francis Guthrie đưa ra bài toán bốn màu về vấn đề liệu chỉ với bốn màu có thể tô màu một bản đồ bất kì sao cho không có hai nước nào cùng biên giới được tô cùng màu. Bài toán này được xem như đã khai sinh ra lý thuyết đồ thị, và chỉ được giải sau một thế kỉ vào năm 1976 bởi Kenneth Appel và Wolfgang Haken. Trong khi cố gắng giải quyết bài toán này, các nhà toán học đã phát minh ra nhiều thuật ngữ và khái niệm nền tảng cho lý thuyết đồ thị.